xDSL is a high-speed data transmission technology for transmitting data over a telephone twisted pair, and comes in two types: DSL which transmits data through baseband, and xDSL which transmits data through passband based on the Frequency Division Multiplexing (FDM) technology. xDSL which transmits data through passband adopts Discrete Multitone Modulation (DMT). A system that provides multiple channels of xDSL access is called as a Digital Subscriber Line Access Multiplexer (DSLAM), whose system reference model is shown in FIG. 1.
Currently, the xDSL technology uses higher and higher frequency bands. Therefore, crosstalk, especially crosstalk on a high frequency band, is more and more noticeable, as shown in FIG. 2. Because the FDM technology is applied to the uplink and downlink channels of the xDSL, near-end crosstalk does not considerably impair the system performance. However, far-end crosstalk deteriorates the transmission performance of the line seriously. When multiple subscriber lines in a bundle of cables need to activate the xDSL service, some lines suffer from low line rates and instable performance or even service activation failure due to the far-end crosstalk, such that the line activation rate of the DSLAM is low.
A subscriber cable generally contains multiple (25 or more) twisted pairs. Different services may run over different twisted pairs. When different xDSL lines work at the same time, crosstalk occurs, and the performance of some lines is deteriorated drastically. As a result, no DSL service can be activated on a long DSL line.
To avoid serious line performance deterioration caused by crosstalk, the International Telecommunication Union-Telecommunication Standardization Sector (ITU-T) proposes a Dynamic Spectrum Management (DSM) solution. The DSM solution aims to enhance the rate, distance and stability of the line by balancing the spectrum dynamically, or send signals at the lowest power while the performance and stability requirements (rate, noise tolerance, and bit error rate) are fulfilled. Through a series of methods, various parameter configurations and the signal Power Spectral Density (PSD) are managed in a centralized and optimized way. Moreover, the transmitting and the receiving of the signals in a whole bundle of cables are coordinated to optimize the line transmission performance. Specifically, DSM eliminates crosstalk by adjusting the transmission power on each modem in the network automatically. Especially in the case that the Central Office (CO) and the Remote Terminal (RT) are mixed, and a short line generates much crosstalk to a long line. As shown in FIG. 3, the impact imposed by line 2 onto line 1 is far greater than the impact imposed by line 1 onto line 2. DSM aims to achieve a balance between maximization of the rate of each modem and minimization of the crosstalk onto other modems by adjusting the transmission power.
FIG. 4 shows a main structure of the first layer of present DSM in the conventional art, which includes a controller: Spectrum Maintenance Center (SMC), and three control interfaces: DSM-S, DSM-C, and DSM-D. The SMC reads parameters such as the working state of the DSL from the DSL-LT through the DSM-D interface, and exchanges information with the correlated SMC through the DSM-S interface. After obtaining sufficient information, the SMC performs a series of optimization calculations, and finally delivers control parameters to the DSL-LT through the DSM-C so that the line works in the best state.
A centralized frequency management algorithm in the first conventional art is Optimum Spectrum Balancing (OSB). It is supposed that N users exist in total, each with K tones, and that N−1 of the users have a target rate. The basic issue of DSM is: on the precondition of fulfilling the rate of the N−1 users, the rate of the first user is increased to the utmost; the energy of each signal needs to meet the PSD requirement; and the total power of each user needs to meet the corresponding constraint
                    ∑                  k          =          1                K            ⁢              S        k        n              ≤          P      n        ,where Pn is the maximum allowable transmission power of n users). Due to non-convexity of this issue, it is necessary to enumerate all possible skn values to work out a complete solution directly. Therefore, the algorithm has the complexity of calculation using both the user quantity (N) and the tone quantity (K) as an exponent, namely, O(eKN). Through a duality method, OCB expresses the foregoing issue as:
                              J          =                                                    max                                                      S                    1                                    ,                  …                  ,                                      S                    N                                                              ⁢                              R                1                                      +                                          ∑                                  n                  =                  2                                N                            ⁢                                                w                  n                                ⁢                                  R                  n                                                      -                                          ∑                                  n                  =                  1                                N                            ⁢                                                ∑                                      k                    =                    1                                    K                                ⁢                                                      λ                    n                                    ⁢                                      S                    k                    n                                                                                      ⁢                                  ⁢                                            s              .              t              .                                                          ⁢              0                        ≤                          s              k              n                        ≤                          s              max                                ,                                          ⁢                      k            =            1                    ,          …          ⁢                                          ,                      K            ;                                                  ⁢                          n              =              1                                ,          …          ⁢                                          ,          N                                    (        1        )            
The target function in formula (1) may be converted into:
                    J        =                                                            ∑                                  k                  =                  1                                K                            ⁢                              b                k                1                                      +                                          ∑                                  n                  =                  2                                N                            ⁢                                                ∑                                      k                    =                    1                                    K                                ⁢                                                      w                    n                                    ⁢                                      b                    k                    n                                                                        -                                          ∑                                  n                  =                  1                                N                            ⁢                                                ∑                                      k                    =                    1                                    K                                ⁢                                                      λ                    n                                    ⁢                                      s                    k                    n                                                                                ⁢                                          ⁢                                          =                                                    ∑                                  k                  =                  1                                K                            ⁢                              (                                                      ∑                                          n                      =                      1                                        N                                    ⁢                                      (                                                                                            w                          n                                                ⁢                                                  b                          k                          n                                                                    -                                                                        λ                          n                                                ⁢                                                  s                          k                          n                                                                                      )                                                  )                                      ⁢                                                  ⁢                                                  =                                          ∑                                  k                  =                  1                                K                            ⁢                              J                k                                                                        (        2        )                                          J          k                =                              ∑                          n              =              1                        N                    ⁢                      (                                                            w                  n                                ⁢                                  b                  k                  n                                            -                                                λ                  n                                ⁢                                  s                  k                  n                                                      )                                              (        3        )            
In the above formulas, w1=1. Considering that Jk is related only to the power allocation sk1, sk2, . . . , skN on tone k and is unrelated to the power allocation on other tones, the maximum value of Jk can be calculated out by enumerating the power allocation of all users on tone k only.
The optimum solution to J can be obtained by calculating max Jk for each independent tone. OSB reduces the calculation complexity to O(KeN) while ensuring availability of the optimum solution.
The implementation process of OSB is detailed below.
For each tone k, (sk1, sk2, . . . , skN)=arg max Jk, k=1, 2, . . . , K is calculated.
For each user n,
                    w        n            =                        [                                    w              n                        +                                          ɛ                n                            ⁡                              (                                                      R                    n                    target                                    -                                                            ∑                                              k                        =                        1                                            K                                        ⁢                                          b                      k                      n                                                                      )                                              ]                +              ,          n      =      2        ,    3    ,    …    ⁢                  ,    N    and                    λ        n            =                        [                                    λ              n                        +                                          ɛ                λ                            ⁡                              (                                                                            ∑                                              k                        =                        1                                            K                                        ⁢                                          s                      k                                              n                        ⁢                                                                                                                                                        -                                      P                    n                                                  )                                              ]                +              ,          n      =      1        ,    2    ,    …    ⁢                  ,    N  are calculated.
The foregoing processes are repeated until the function converges.
At the time of calculating sk1, sk2, . . . , skN which makes Jk maximum, no simple analytical solution exists because Jk is a non-convex function.
Therefore, to obtain the optimum solution to sk1, sk2, . . . , skN, all skn values need to be enumerated on the space of [0, smax]N. After a round of enumeration is completed, wn and λn are adjusted dynamically according to the extent of fulfilling the constraint conditions. If a constraint condition is already fulfilled, it is necessary to decrease the value of wn or λn on the corresponding subscriber line to reduce the impact of this constraint condition on the whole target function. If a constraint condition is not fulfilled, it is necessary to increase the value of wn or λn on the corresponding subscriber line to increase the weight of this constraint condition in the whole target function. The algorithm repeats the foregoing operations until all constraint conditions are fulfilled and the power allocation never changes again. In this circumstance, the algorithm can be regarded as having converged.
The OSB algorithm can obtain a calculation result within an acceptable time range when the user quantity “N” is not too large. However, when the user quantity increases, the calculation time increases exponentially. In a word, the merits of the OSB algorithm are optimum, and, when N is small, computability. OSB provides high performance, but it is too complex and not user-definable, and requires a central manager to exchange data. Therefore, OSB is not practical at all. Many quasi-optimum algorithms are derived from OSB, for example, Iterative Spectrum Balancing (ISB). Compared with OSB, such algorithms are much simpler, but still involve a huge calculation burden in the practical work, especially when many lines exist.
A distributed frequency management algorithm available in the second conventional art is Iterative Water Filling (IWF).
IWF is a greedy algorithm. It considers only the impact of the skn change on the rate of line n, without considering interference onto other lines from the optimization perspective.
The target function Jk of IWF may be expressed as JkJkn=wnbkn−λnskn.
The implementation process of IWF is detailed below.
The following process is performed for each user n (n=1, 2, . . . , N).
For each tone k, Skm, ∀m≠n, is fixed, and wm=0, ∀m≠n, is supposed; skn=arg max (wnbkn−λnskn) is calculated.
If
                    ∑                  k          =          1                K            ⁢              s        k        n              >          P      n        ,          ⁢            λ      n        =                  [                              λ            n                    +                      ɛ            ⁡                          (                                                                    ∑                                          k                      =                      1                                        K                                    ⁢                                      s                    k                    n                                                  -                                  P                  n                                            )                                      ]            +      is executed; otherwise,
      λ    n    =            [                        λ          n                +                  ɛ          ⁡                      (                                                            ∑                                      k                    =                    1                                    K                                ⁢                                  b                  k                  n                                            -                              R                n                target                                      )                              ]        +  is executed until the function converges.
IWF is less complex, and is still computable if the values of N and K are large. Moreover, IWF is completely autonomous. That is, each user needs to optimize only their own rate and fulfill their own power constraint, without requiring different users to exchange data. In other words, no central manager is required. Therefore, IWF is easily practicable in the actual system. However, IWF is a greedy algorithm. Its performance is low when the crosstalk environment is complex, and cannot ensure the optimum solution or quasi-optimum solution.